import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * Created by L.jp
 * Description:给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
 *
 *输入: nums = [0,1,0]
 * 输出: 2
 * 说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。
 * User: 86189
 * Date: 2021-11-06
 * Time: 21:05
 */
//找有相同数量的0和1的子串，那么就可以把问题转换为计算前缀和为0的子串，把0当做-1,1就是1，这样数量相等的话那么就是前缀和为0

public class ContinuousArray {
    public static int findMaxLength(int[] nums){
        Map<Integer,Integer> map=new HashMap<>();
        int prenum=0;//前缀和
        int maxlength=0;//连续最大长度
        map.put(0,-1);//把前缀合放入key值，把前缀和的对应下标放入value值
        for(int i=0;i<nums.length;i++){
            prenum=prenum+(nums[i]==1 ?1 :-1);//前缀和问题，只有0和1，把0当做-1,1就是1，这样在计算前缀和的时候，如果0和1数量相等，那么前缀和就是0；
            if(map.containsKey(prenum)){
                maxlength=Math.max(maxlength,i-map.get(prenum));//每到一个下标，就计算一次前缀和，如果相同的前缀和再次出现，就计算一次连续最大长度，
                                                                // 利用数学函数让当前下标和上次相同前缀和的下标相减，跟上一次的最大长度比较
            }else{
                map.put(prenum,i);
            }
        }
        return maxlength;
    }
    public static void main(String[] args) {
        int[] nums={0,1,0};
        System.out.println(findMaxLength(nums));
    }
}
